package leetcode;

/*
367. 有效的完全平方数
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如  sqrt。
示例 1：
输入：16
输出：True
示例 2：
输入：14
输出：False
*/

public class problems_367 {
    public static void main(String[] args) {
        System.out.println(new Solution().isPerfectSquare(4));
    }

    static class Solution {
        public boolean isPerfectSquare(int num) {
            if (num < 2) return true;
            long x = num / 2;
            while (x * x > num) {
                x = (x + num / x) / 2;
            }
            return (x * x == num);
        }
    }

//    static class Solution {
//        // 二分法
//        int min = 0;
//        int max = 0;
//        public boolean isPerfectSquare(int num) {
//            if(num == 1) return true;
//            max = num;
//            while (max > min) {
//                int tempNum = (min + max) / 2;
//                int ret = tempNum * tempNum;
//                if (ret > num) {
//                    if(max == tempNum) return false;
//                    max = tempNum;
//                } else if (ret < num) {
//                    if(min == tempNum) return false;
//                    min = tempNum;
//                } else {
//                    return true;
//                }
//            }
//            return false;
//        }
//    }
}